185A - Plant - CodeForces Solution

//multiplication of two matrix in O(n3);
#include<bits/stdc++.h>
using namespace std;
int MOD= 1000000007;
vector<vector<long long>> multiply(vector<vector<long long>> v1, vector<vector<long long>> & v2){
    vector<vector<long long>> ans(v1.size(),vector<long long>(v1.size(), 0));
    for(long long i=0;i<v1.size();i++){
        for(long long j=0;j<v2.size();j++){
            long long sum=0;
            for(long long k=0;k<v2.size();k++){
                sum+= (v1[i][k]*v2[k][j])%MOD;
                sum = sum%MOD;
            }
            ans[i][j]= sum;
        }
    }
    return ans;
}
 
vector<vector<long long>> matrixExpo(vector<vector<long long>> &a, long long n){
    if(n==0){
       vector<vector<long long>> ans(a.size(), vector<long long>(a.size(), 0));
       for(long long i=0;i<a.size();i++){
         ans[i][i]=1;
       }
       return ans;
    }
    if(n==1){
        return a;
    }
    vector<vector<long long>> temp = matrixExpo(a, n/2);
    vector<vector<long long>> ans = multiply(temp, temp);
    if(n%2!=0){
        ans = multiply(ans, a);
    }
    return ans;
}
void solve(){
    long long n; cin>>n;
    if(n==0){
        cout<<1;
        return;
    }
    n--;
    vector<vector<long long>> a= {{6, -8}, {1, 0}};
    vector<vector<long long>> ans = matrixExpo(a, n);
    long long val = ((ans[0][0]*3)%MOD +(ans[0][1])%MOD)%MOD;
    if(val<0){
        val = val+MOD;
    }
    cout<<val;
}
int main()
{
 long long t=1;
 for(long long it=1;it<=t;it++) {
     solve();
 }
 return 0;
}